1. Field of the Invention
The present invention relates to a Reed-Solomon decoder, and more particularly to a polynomial evaluation circuit used to determine error-locator polynomial roots in a Reed-Solomon decoder.
2. State of the Art
Error correction is the process of detecting bit errors and correcting them in a system which transmits information in a binary format. Error correction is implemented by decoding a codeword including information and parity bits to facilitate the detection and correction of the bit errors.
There are several types of error correcting codes used to encode information bits for error detection and/or correction. In particular, the Reed-Solomon error correcting code is a widely implemented code since it has increased error correction capability compared to other known error correcting codes. A typical notation for this type of code is RS(m,d) wherein m is the codeword length and d is the number of information bytes in the codeword.
Reed-Solomon codes are constructed from symbols or bytes (where one byte is equal to p-bits) from a finite or Galois Field (GF) of elements. For instance, a GF(2p) is a finite field of 2p codewords, where m=2pxe2x88x921 is the codeword length. The elements of a Reed-Solomon error correcting code which are defined over a Galois field can be represented as polynomials having associated powers and coefficients.
In general, a Reed-Solomon error detection and correction system includes an encoder portion for encoding d information bytes into a codeword of m bytes and a decoder portion for receiving the Reed-Solomon codeword of m bytes for detecting and correcting any errors. FIG. 1 shows one prior art decoder system architecture which can be generally described as a Reed-Solomon forward error correction decoder. A Reed-Solomon decoder includes several stages for evaluating the received codewords to obtain information for performing the error correction/detection. For instance, as shown in FIG. 1, an error polynomial stage determines an error-locator polynomial. This stage is followed by an error locator stage which functions to determine the roots of the error-locator polynomial. The results provided by the error-locator polynomial are then used in the remainder of the decoding system to perform error correction.
Reed-Solomon codes can be characterized as being unshortened or shortened code. In the case of an unshortened code, the number of codewords in the Reed-Solomon code is the same number of possible elements in the Galois Field that the RS code is defined over. In the case of an shortened code, the number of codewords in the Reed-Solomon code is less than the number of possible elements in the Galois Field that the RS code is defined over. Put into mathematical terms, a RS(m,d) unshortened code defined over the Galois Field GF(2p), where m=2pxe2x88x921, has a total codeword length of m bytes where d of the bytes are information bytes. A shortened RS(n,k) code, where RS(n,k)=RS(m, mxe2x88x92n+k), defined over the Galois Field GF(2p), where m=2pxe2x88x921, has a total codeword length of n bytes with k information bytes.
In the prior art as described in xe2x80x9cOn the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arraysxe2x80x9d, H. M. Shao, I. S. Reed, IEEE Transactions on Computers, vol. C-37, No. 10, pp. 1273-1280, October 1988, and in xe2x80x9cError Control Coding: Fundamentals and Applicationsxe2x80x9d, D. J. Costello, S. Lin, New Jersey: Prentice-Hall, 1983, several error-locator polynomial roots determination circuits are proposed. FIGS. 1B and 1C described in xe2x80x9cOn the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arraysxe2x80x9d show two determination circuits. The circuits include cell(1)xe2x88x92cell(dxe2x88x921), each utilizing feedback multipliers 10 in the critical timing data path 11 of the circuit. The feedback multipliers 10 represent a significant combinational logic operation of a field element 12 and a coefficient stored in the register device 13. Cell(1)xe2x88x92cell(dxe2x88x921) shown in FIG. 1C are implemented with the same cell structure as shown in FIG. 1B.
As a result of the manner in which each of the prior art circuits are implemented the overall performance of the determination circuits shown in FIGS. 1B and 1C are degraded. More specifically, the optimal number of clock cycles to determine the error-locator polynomial roots in a real time RS decoder with unshortened code which receives back-to-back input frames (one frame=m data bytes) is m or less clock cycles. Similarly, the optimal number of clock cycles to determine the error-locator polynomial roots in a real time RS decoder with shortened code which receives back-to-back input frames (one frame=n data bytes) is n or less clock cycles. However, since each of the prior art circuit designs include a computation intensive logical multiplication step in a critical timing path it takes more than the above irritated optimal amount of time to determine the error-locator polynomial roots.
The present invention determines the error-locator polynomial roots faster than prior art methods by using a high speed pre-computing stage and eliminating the logical multiplication operation from the critical path.
The present invention is a system and method of determining error-locator polynomial roots in a Reed-Solomon decoder by evaluating a set of expanded error-locator polynomials. A first embodiment of the system and method are implemented to facilitate decoding of an unshortened Reed-Solomon (RS) error correcting code and a second embodiment of the system and method are implemented to facilitate decoding of a shortened RS code.
The improved system and method of evaluating an error-locator polynomial to determine the error locator roots of the polynomial in a Reed-Solomon decoder includes a pre-computing logical operation step followed by a feedback logical operation step. The pre-computing step obviates the need to include constant Galois Field multipliers in the critical path in the polynomial evaluation circuit thereby resulting in fast error locator root determination.
In the system and method used in a Reed-Solomon (RS) decoder to determine roots of error locator polynomials, a first pre-computation operation is performed to obtain a p-bit polynomial solution value in a first clock cycle and second parallel feedback logical operations are performed to obtain a p-bit polynomial solution value in each subsequent clock cycle. The system excludes constant Galois Field multipliers from the critical timing path of the system so as to facilitate high speed error-locator polynomial root determination. In the case of an unshortened RS(m,d) decoder defined over the Galois Field GF(2p) where GF(2p) is a finite field of 2p elements and m=2pxe2x88x921, final root location values are obtained in m cycles. In the case of a shortened RS(n,d) decoder defined over the Galois Field GF(2p) where GF(2p) is a finite field of 2p elements and m=2pxe2x88x921 and n less than m, final root location values are obtained in n cycles.
In accordance with one embodiment of the method of error-locator polynomial root determination which is implemented using a RS(m,d) unshortened code defined over a Galois Field GF (2p) where m=2pxe2x88x921 is the codeword length in bytes, d is the number of information bytes, and t=(mxe2x88x92d)/2 is the number of bytes which can be corrected per codeword. During a first clock cycle, t pre-compute parallel logical operations are performed between t p-bit coefficient values and t p-bit root values to determine a set of t p-bit pre-computed partial resultant values which are stored in t registers and are summed to determine a p-bit value representing a polynomial solution to one of a set of expanded error-locator polynomials. In each of the (mxe2x88x921) clock cycles subsequent the first clock cycle, a new set of t p-bit partial root location values are determined, stored, and summed to determine (mxe2x88x921) p-bit polynomial solution values. As a result, root location values for an unshortened Reed-Solomon code (i.e., RS(m,d)) can be determined in a total of m clock cycles.
In accordance with another embodiment of the method of error-locator polynomial root determination which is implemented using a RS(n,k) decoder implemented as a shortened RS(m,mxe2x88x92n+k) code defined over a Galois Field GF (2p) where n is the codeword length in bytes, k is the number of information bytes, and t=(nxe2x88x92k)/2 is the number of bytes which can be corrected per codeword. During a first clock cycle, t initial parallel logical operations are performed between t p-bit coefficient values and t p-bit root values to determine a set of t p-bit partial resultant values which are stored in t registers and are summed to determine a p-bit value representing a polynomial solution to one of a set of expanded error-locator polynomials. In each of the (nxe2x88x921) clock cycles subsequent the first clock cycle, a new set of t p-bit partial resultant values are determined, stored, and summed to determine (nxe2x88x921) p-bit polynomial value solutions. As a result, root location values for an unshortened Reed-Solomon code (i.e., RS(n,d)) are determined in a total of n clock cycles.
An embodiment of the system for evaluating an error-locator polynomial includes a plurality of circuit branches, each circuit branch corresponding to one of a plurality of p-bit polynomial root coefficient values and each branch including a pre-computing stage and a feedback loop stage. The pre-computing stage performs an initial logical operation between a p-bit polynomial coefficient value and an initial p-bit root value to generate a p-bit pre-computed partial resultant value in a first clock cycle. The first set of p-bit pre-computed partial resultant values from all of the branches are passed through to a summation stage and are summed to generate a p-bit solution value of a first one of a set of expanded error locator polynomials at the output of the system. After the first clock cycle, the individual branch p-bit pre-computed partial resultant values are fed back to the feedback loop stage in each branch which performs logical operations to generate a new set of p-bit partial resultant values in each subsequent clock cycle. In each subsequent clock cycle, the new set of p-bit resultant value solutions are stored in the registers and are summed to generate a p-bit solution value to each of the remaining expanded error locator polynomials. The p-bit value solutions are then used to determine the roots of the expanded error locator polynomial.
The feedback loop stage is characterized in that due to the pre-computing stage, a constant Galois Field multiplication operation is not performed in the critical timing path of each of the plurality of circuit branches. As a result, root location information for an unshortened RS(m,d) code as defined above are determined in a total of m clock cycles and root location information for a shortened RS(n,k) code as defined above are determined in a total of n clock cycles.
A first embodiment of the system for error-locator polynomial root determination is designed for a decoder using an unshortened code and a second embodiment of the system for error-locator polynomial root determination is designed for a decoder using a shortened code.